/**
 * @ClassName : _748_最短补全词
 * @Author : 骆发茂
 * @Date: 2021/12/10 19:47
 * @Description : https://leetcode-cn.com/problems/shortest-completing-word/
 */
public class _748_最短补全词_彤哥来刷题啦 {
    //根据题意，先对 licensePlatelicensePlate 进行词频统计（忽略空格和数字），然后遍历 wordswords 进行词频统计，
    // 从所有符合要求的 words[i]words[i] 找到最短的补全词。
    class Solution {
        public String shortestCompletingWord(String licensePlate, String[] words) {
            int[] lcnt = new int[26];
            for (int i = 0; i < licensePlate.length(); i++) {
                if (Character.isLetter(licensePlate.charAt(i))) {
                    lcnt[Character.toLowerCase(licensePlate.charAt(i)) - 'a']++;
                }
            }

            String ans = null;
            for (String word : words) {
                if (check(word, lcnt) && (ans == null || ans.length() > word.length())) {
                    ans = word;
                }
            }
            return ans;
        }

        private boolean check(String word, int[] lcnt) {
            int[] wcnt = new int[26];
            for (int i = 0; i < word.length(); i++) {
                wcnt[word.charAt(i) - 'a']++;
            }

            for (int i = 0; i < 26; i++) {
                if (lcnt[i] > wcnt[i]) {
                    return false;
                }
            }

            return true;
        }
    }

}